Apabila penduduk Australia yang pertama tiba di pantai barat laut 40,000 hingga 60,000 tahun yang lalu, paras laut jauh lebih rendah. Pantai Kimberley pada satu masa hanya kira-kira 90 km dari Timor, yang laluan itu sendiri ialah garis pulau rapat yang terakhir dalam bagi manusia untuk jalan menyeberang.[4] Maka, ini adalah mungkin (walaupun kemungkinan) lokasi pendatang Australia yang pertama tiba melalui beberapa buah bot primitif. Laluan penghijrahan mungkin lain ialah melalui pulau-pulau di sebelah utara dan kemudian melalui New Guinea.

Selama puluhan ribu tahun seterusnya penduduk asli Australia perlahan-lahan bergerak ke selatan dan ke timur merentasi daratan. Orang asli telah lama menetap di seluruh Australia Barat pada masa kapal-kapal Eropah mula secara tidak sengaja tiba dalam perjalanan ke Batavia (kini Jakarta) pada abad ke-17 awal.